689D - Friends and Subsequences - CodeForces Solution

# include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 5;
int a[22][N], b[22][N], n, Log[N];
int query(int l,int r,int opt) // 0-a 1-b
{
	int mid = Log[r - l + 1]; 
	if(opt) return min(b[mid][l], b[mid][r - (1 << mid) + 1]);
	else return max(a[mid][l], a[mid][r - (1 << mid) + 1]);
}
int main(void)
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[0][i]);
	for(int i = 1; i <= n; i++) scanf("%d", &b[0][i]);
	Log[1] = 0, Log[2] = 1;
	for(int i = 3; i <= n; i++) Log[i] = Log[i / 2] + 1; 
	for(int i = 1; (1 << i) <= n; i++)
	{
		for(int j = 1; j + (1 << i) - 1 <= n; j++)
		{
			a[i][j] = max(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
			b[i][j] = min(b[i - 1][j], b[i - 1][j + (1 << (i - 1))]);
		}
	}
	i64 ans = 0;
	for(int L = 1; L <= n; L++)
	{
		int r1 = -1, r2 = -1;
		if(query(L,L,0) > query(L,L,1) || query(L,n,0) < query(L,n,1)) continue;
		if(query(L,L,0) == query(L,L,1)) r1 = L;
		
		else 
		{
			int l = L, r = n; 
			while(l <= r)
			{
				int mid = (l + r) >> 1; 
				if(query(L,mid,0) >= query(L,mid,1)) 
				{
					r1 = mid, r = mid - 1;
				}
				else l = mid + 1;
			}
			if(r1 == -1 || query(L,r1,0) > query(L,r1,1)) continue;
		}
		int l = r1, r = n;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(query(L,mid,0) == query(L,mid,1)) 
			{
				r2 = mid, l = mid + 1;
			}
			else r = mid - 1;
		}
//		printf("L = %d,r1 = %d, r2 = %d\n",L,r1,r2);
		ans += (r2 - r1 + 1);
	}
	printf("%lld\n",ans);
	return 0;
}